package com.wl2o2o.lanqiao.xzfourteen;


public class FibWithHelper {
	static int  cnt1 = 0;
	static int  cnt2 = 0;
	static int  cnt3 = 0;
	
	public static void main(String[] args) {
		System.out.println(fib1(100)+",剪枝后递归迭代了："+cnt2+"次");
		System.out.println(fib2(100)+",状压dp运行了："+cnt3+"次");
		
		System.out.println(Fib(100)+",普通迭代运行了："+cnt1+"次");
		
	}
	//-------------------方法一-------------------------
	//普通递归方法求fib，时间复杂度：O(2^n)
	public static int Fib(int n) {
		cnt1++;
		if(n == 0)return 0;
		if(n ==1 || n ==2)return 1;
//		System.out.println(Fib(n-1)+Fib(n-2));
		return  Fib(n-1)+Fib(n-2);
		
	}
	//-------------------方法二--------------------------
	//动态规划，递归＋数组备忘录（空间换时间）
	//带备忘录的递归解法
	public static int fib1(int N) {
		if(N == 0) {
			return 0;
		}
		int[] a = new int[N+1];
		return helper(N, a);
		
	}
	public static int helper(int n, int[] a) {
		cnt2++;
		if(n == 1 || n ==2)return 1;
		//剪枝：
		if(a[n] != 0)return a[n];
		//开枝散叶
		a[n] = helper(n-1, a) + helper(n-2, a);
		return a[n];
	}
	//-------------------方法三-------------------------
	//状态压缩，只记录有用的数据
	public static int fib2(int n) {
		int prev = 1, cur = 1;
		int sum =0;
		for(int i = 3; i <= n; i++) {
			cnt3++;
			sum = prev + cur;
			prev = cur;
			cur = sum;
		}
		return sum;
	}

}
